{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Reverse a String\n",
    "\n",
    "This interview question requires you to reverse a string using recursion. Make sure to think of the base case here.\n",
    "\n",
    "Again, make sure you use *recursion* to accomplish this. **Do not slice (e.g. string[::-1]) or use iteration, there muse be a recursive call for the function.**\n",
    "\n",
    "____\n",
    "\n",
    "## Solution\n",
    "\n",
    "In order to reverse a string using recursion we need to consider what a base and recursive case would look like. Here we've set a base case to be when the length of the string we are passing through the function is length less than or equal to 1.\n",
    "\n",
    "During the recursive case we grab the first letter and add it on to the recursive call."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse(s):\n",
    "    \n",
    "    # Base Case\n",
    "    if len(s) <= 1:\n",
    "        return s\n",
    "\n",
    "    # Recursion\n",
    "    return reverse(s[1:]) + s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'dlrow olleh'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverse('hello world')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Test Your Solution\n",
    "\n",
    "Run the cell below to test your solution against the following cases:\n",
    "\n",
    "    string = 'hello'\n",
    "    string = 'hello world'\n",
    "    string = '123456789'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PASSED ALL TEST CASES!\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "RUN THIS CELL TO TEST YOUR FUNCTION AGAINST SOME TEST CASES\n",
    "'''\n",
    "\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestReverse(object):\n",
    "    \n",
    "    def test_rev(self,solution):\n",
    "        assert_equal(solution('hello'),'olleh')\n",
    "        assert_equal(solution('hello world'),'dlrow olleh')\n",
    "        assert_equal(solution('123456789'),'987654321')\n",
    "        \n",
    "        print 'PASSED ALL TEST CASES!'\n",
    "        \n",
    "# Run Tests\n",
    "test = TestReverse()\n",
    "test.test_rev(reverse)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extra Notes\n",
    "\n",
    "The \"trick\" to this question was thinking about what a base case would look like when reversing a string recursively. It takes a lot of practice to be able to begin thinking like this, so don't worry if you're struggling! However it is important to fully understand the solution!\n",
    "\n",
    "**Good Job!**"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
